這題要在一個完美二元樹（每個節點都有兩個子節點，且葉節點在同一層）中，把每個節點的 next 指針指向它的右邊相鄰節點，如果沒有右邊相鄰節點，就把 next 指針設成 null，這題的目的是要實現一個在不額外用空間（不用額外的資料結構）的情況，改樹中節點的指標指向，讓每層的節點通過 next 指針連起來。

思路：
完全二元樹的特性，因是一個完美二元樹，每個父節點都有兩個子節點，且每層的葉節點都在同一層，所以可以透過父節點的連接來處理子節點的連接，從頂層開始，可以從根節點開始，逐層遍歷，然後把每個節點的左右子節點設 next 指針就是把當前層的節點 left 指向 right，再把 right 指向下一個節點的 left，如果那個節點存在 next 的話。
遞迴或迭代，因為可以在樹結構中用指標解決這個問題，用遞迴遍歷每層節點，也可以用迭代的方式從頂層慢慢處理到下一層。
（不用額外的空間，只利用 O(1) 的額外記憶體空間來解決問題，通過直接改節點的 next 指針完成）

步驟：
從根節點開始，逐層向下遍歷，對每層的節點，連接它的左右子節點，再把它的右子節點跟它的下一個節點的左子節點連接，重複這個步驟，直到所有節點的 next 指針都設完畢。

程式碼：
#Definition for a Node.
class Node(object):
def init(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next

class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root:
return None

    #從最左邊的節點開始遍歷
    leftmost = root
    
    #當最左邊的節點有左子節點時
    while leftmost.left:
        # 遍歷這一層的節點
        head = leftmost
        while head:
            # 把左子節點的 next 指向右子節點
            head.left.next = head.right
            
            #如果 head 有下一個節點，把當前右子節點的 next 指向下一個節點的左子節點
            if head.next:
                head.right.next = head.next.left
            
            #移動到這一層的下一個節點
            head = head.next
        
        #移動到下一層的最左邊節點
        leftmost = leftmost.left
    
    return root

解釋：
從根節點開始，先檢查根節點是不是空，如果是空樹就直接返回 None，逐層處理，從樹的最左邊開始，每次處理一層的節點，連接左、右子節點，當有一個節點 head，先把它的左子節點的 next 指向它的右子節點，連接相鄰節點，如果當前節點 head 有 next 節點，那就把當前節點的右子節點的 next 指向 head.next 的左子節點，再到下層，一層處理完成後，移動到下一層的最左節點，繼續處理。

時間複雜度：O(n)， n 是樹中的節點總數，每個節點被訪問一次，所以總時間複雜度是 O(n)。
空間複雜度：O(1)，除了遞迴棧外，沒有用額外的空間，所以是常數。
技巧：
理解完全二元樹的特性，這個題目針對完全二元樹的特殊情況，所以可以利用這個特性來優化解法，不用額外的記憶體，指標的運用，在樹的節點間建立關聯，合理用節點的指標修改關鍵在需要連接多個子節點時，逐層處理每個節點的 next 指針，從上到下ㄧㄧ設置，可避免處理順序混亂，最後是優化使用空間，這道最主要的要求就是實現 in-place 的修改，為的就是減少空間複雜度，對於記憶體使用的理解需要更全面。